package com.likeycy.my.sort;

import com.likeycy.my.sort.cmp.Sort;

/**
 * @ClassName: RadixSort
 * @Description: 基数排序:另一种实现思路
 * @Author: sodagreen
 * @Date: 2021/4/3 12:44
 * @Version: 1.0
 */
public class RadixSort1 extends Sort<Integer> {

    @Override
    protected void sort() {
        // 先找到数组中的最大值，好确定最高位是个、十、百、千、万……中的哪一位。这样可以确定需要排多少轮
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        bucketSort(max);

    }

    private void bucketSort(int max) {

        // 桶数组
        int[][] buckets = new int[10][array.length];
        // 每个桶的元素数量
        int[] bucketSizes = new int[buckets.length];

        // 假设 max = 5963
        // 个位数：5963 / 1 % 10 = 3
        // 十位数：5963 / 10 % 10 = 6
        // 百位数：5963 / 100 % 10 = 9
        // 千位数：5963 / 1000 % 10 = 5
        for (int divider = 1; divider <= max; divider *= 10) {
            for (int i = 0; i < array.length; i++) {
                // 取出数组中每个数当前个位、十位、百位……上的数
                int no = array[i] / divider % 10;
                buckets[no][bucketSizes[no]++] = array[i];
            }
            int index = 0;
            for (int i = 0; i < buckets.length; i++) {
                for (int j = 0; j < bucketSizes[i]; j++) {
                    array[index++] = buckets[i][j];
                }
                bucketSizes[i] = 0;
            }
        }
    }
}
